import java.util.Stack;

/**
 * 856. 括号的分数
 *
 * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
 *
 *     () 得 1 分。
 *     AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 *     (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 * 示例 1：
 * 输入： "()"
 * 输出： 1
 *
 * 示例 2：
 * 输入： "(())"
 * 输出： 2
 *
 * 示例 3：
 * 输入： "()()"
 * 输出： 2
 *
 * 示例 4：
 * 输入： "(()(()))"
 * 输出： 6
 *
 * 提示：
 *     S 是平衡括号字符串，且只含有 ( 和 ) 。
 *     2 <= S.length <= 50
 */
public class Solution_856 {
    public int scoreOfParentheses(String S) {
        char[] chars = S.toCharArray();
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (char c : chars) {
            if (c == '(') {
                stack.push(0);
            }else {
                Integer v = stack.pop();
                Integer w = stack.pop();
//                if (v == 0) {
//                    stack.push(w + 1);
//                }else {
//                    stack.push(w + v*2);
//                }
                stack.push(w + Math.max(v*2,1));
            }
        }
        return stack.pop();
    }
}
